/*
 * @lc app=leetcode.cn id=558 lang=typescript
 *
 * [558] 四叉树交集
 */

// @lc code=start
/**
 * Definition for node.
 * class Node {
 *     val: boolean
 *     isLeaf: boolean
 *     topLeft: Node | null
 *     topRight: Node | null
 *     bottomLeft: Node | null
 *     bottomRight: Node | null
 *     constructor(val?: boolean, isLeaf?: boolean, topLeft?: Node, topRight?: Node, bottomLeft?: Node, bottomRight?: Node) {
 *         this.val = (val===undefined ? false : val)
 *         this.isLeaf = (isLeaf===undefined ? false : isLeaf)
 *         this.topLeft = (topLeft===undefined ? null : topLeft)
 *         this.topRight = (topRight===undefined ? null : topRight)
 *         this.bottomLeft = (bottomLeft===undefined ? null : bottomLeft)
 *         this.bottomRight = (bottomRight===undefined ? null : bottomRight)
 *     }
 * }
 */

var intersect = function (quadTree1, quadTree2) {
  // q1为叶子节点，
  if (quadTree1.isLeaf) {
    // q1的值为1的时候，结果可以直接合并，返回新节点
    if (quadTree1.val) {
      return new Node(true, true);
    }
    // q1的值为0的时候，返回q2的节点值
    return new Node(
      quadTree2.val,
      quadTree2.isLeaf,
      quadTree2.topLeft,
      quadTree2.topRight,
      quadTree2.bottomLeft,
      quadTree2.bottomRight
    );
  }
  // q2是叶子节点，采取q1的操作
  if (quadTree2.isLeaf) {
    return intersect(quadTree2, quadTree1);
  }
  const o1 = intersect(quadTree1.topLeft, quadTree2.topLeft);
  const o2 = intersect(quadTree1.topRight, quadTree2.topRight);
  const o3 = intersect(quadTree1.bottomLeft, quadTree2.bottomLeft);
  const o4 = intersect(quadTree1.bottomRight, quadTree2.bottomRight);

  // 合并节点，当前节点的4个子节点都是叶子节点且值都相同，可以将当前节点合并为1个叶子节点
  if (
    o1.isLeaf &&
    o2.isLeaf &&
    o3.isLeaf &&
    o4.isLeaf &&
    o1.val === o2.val &&
    o1.val === o3.val &&
    o1.val === o4.val
  ) {
    return new Node(o1.val, true);
  }

  return new Node(false, false, o1, o2, o3, o4);
};

// @lc code=end
